This invention relates generally to data communications and more particularly to packet classification in data communication systems.
Data in data communication systems are often transported in packet form. Packets include data and headers that direct the packet through the data communications network to its final destination. Routing information and other properties, such as billing information and priority, is often extracted from the packet by examining the headers at various points in the network. This type of packet classification by switches and other entities within the data communications network can require a great deal of processing bandwidth and also introduce latency in the system if it cannot be accomplished in a timely manner.
The header information of the data communications packet typically includes a source address that indicates the source of the data communications packet, a destination address that indicates the intended receiver of the packet, the particular protocol that is being used to transport the data, and other relevant information used to determine how the data packet should be treated throughout the data communication system. In order to classify the data packet and determine how it should be dealt with, the header information is examined. In a firewall application, the header information may be utilized to determine whether or not data can be passed through a particular link in the data communications system. If the packet is passed, it must be prioritized relative to other packets destined for the same link, which may be based on the class of service. In other applications, the header information may be used to determine billing information such as the cost of sending the data packet and which party is to be billed.
Data communication protocols are often structured using a number of different layers, where each layer may include a number of parameters associated with a particular data packet. Typically, these parameters are included in the header of the data packet. Thus, the parameters contained in the header of the data packet can be significant. These parameters must be efficiently assessed and processed in order to properly utilize them for routing and other data classification purposes.
Prior art solutions to the problem of filtering or classifying packets using the large amount of information contained in the packet headers include mathematically elegant solutions that are able to sort through the data in the packet header. However, these prior art solutions typically encounter problems with memory usage. In many cases the large amount of memory required to store the classification parameters required to properly analyze incoming packets renders these solutions impractical for most applications. Although the use of cache memories can help alleviate some of the obstacles created by large memory requirements, the bandwidth required to update the contents of the cache render these solutions impractical.
Similarly, in systems that have more reasonable memory requirements, the algorithms required to perform the packet classification are time consuming to the point where the delay introduced is detrimental to the system performance. In addition to this, the parameters used for classification in these systems are often stored in such a way that it is difficult to modify the classification parameters, or rules. Because the parameters used to classify the packets are often dynamic, the ability to easily modify the parameters is important in most applications.
Therefore, a need exists for a method and apparatus for packet classification that requires a limited amount of memory, is able to perform the classification in a timely manner, and allows for easy modification of the rules, or classification parameters.